package q692_topKFrequent;

import java.util.*;

public class Solution_2 {
    /*
    与solution1不同的思路：
    对于这种需要取出前k个题型 我们也可以使用优先队列的方法
    首先同样将所有的word与次数加入到map中
    然后编写一个优先队列 按照出现次数 （从小到大） 排列
    这样排列的方式使得我们可以在队列超过k个时 弹出队头的元素 也就是此时出现次数最少的元素
    最后将队列中所有的word依次弹出放到list中 由于是从小到大排列 所以需要reverse
     */
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        List<String> res = new ArrayList<>();
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((a, b) -> Objects.equals(a.getValue(), b.getValue()) ? b.getKey().compareTo(a.getKey()) : a.getValue() - b.getValue());
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k) pq.poll();
        }

        while (!pq.isEmpty()) res.add(pq.poll().getKey());
        Collections.reverse(res);
        return res;
    }
}
